{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimize the Difference Between Target and Chosen Elements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimizeTheDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小化目标值与所选元素的差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的整数矩阵 <code>mat</code> 和一个整数 <code>target</code> 。</p>\n",
    "\n",
    "<p>从矩阵的 <strong>每一行</strong> 中选择一个整数，你的目标是&nbsp;<strong>最小化</strong>&nbsp;所有选中元素之&nbsp;<strong>和</strong>&nbsp;与目标值 <code>target</code> 的 <strong>绝对差</strong> 。</p>\n",
    "\n",
    "<p>返回 <strong>最小的绝对差</strong> 。</p>\n",
    "\n",
    "<p><code>a</code> 和 <code>b</code> 两数字的 <strong>绝对差</strong> 是 <code>a - b</code> 的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/03/matrix1.png\" style=\"width: 181px; height: 181px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2,3],[4,5,6],[7,8,9]], target = 13\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>一种可能的最优选择方案是：\n",
    "- 第一行选出 1\n",
    "- 第二行选出 5\n",
    "- 第三行选出 7\n",
    "所选元素的和是 13 ，等于目标值，所以绝对差是 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/03/matrix1-1.png\" style=\"width: 61px; height: 181px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1],[2],[3]], target = 100\n",
    "<strong>输出：</strong>94\n",
    "<strong>解释：</strong>唯一一种选择方案是：\n",
    "- 第一行选出 1\n",
    "- 第二行选出 2\n",
    "- 第三行选出 3\n",
    "所选元素的和是 6 ，绝对差是 94 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/08/03/matrix1-3.png\" style=\"width: 301px; height: 61px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2,9,8,7]], target = 6\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>最优的选择方案是选出第一行的 7 。\n",
    "绝对差是 1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 70</code></li>\n",
    "\t<li><code>1 &lt;= mat[i][j] &lt;= 70</code></li>\n",
    "\t<li><code>1 &lt;= target &lt;= 800</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimize-the-difference-between-target-and-chosen-elements](https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimize-the-difference-between-target-and-chosen-elements](https://leetcode.cn/problems/minimize-the-difference-between-target-and-chosen-elements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5,6],[7,8,9]]\\n13', '[[1],[2],[3]]\\n100', '[[1,2,9,8,7]]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        # 最小的大于等于 target 的和\n",
    "        large = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            next_large = float(\"inf\")\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    if j + x >= target:\n",
    "                        next_large = min(next_large, j + x)\n",
    "                    else:\n",
    "                        g.add(j + x)\n",
    "                next_large = min(next_large, large + x)\n",
    "            f = g\n",
    "            large = next_large\n",
    "        \n",
    "        ans = abs(large - target)\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cur = 1 ## 初始状态只有一个和：0\n",
    "        for i in range(m):\n",
    "            tmp = 0\n",
    "            for j in range(n):\n",
    "                tmp |= cur << mat[i][j] ## 左移n位，代表所有和都加n\n",
    "            cur = tmp\n",
    "        res = 0\n",
    "        left = right = 1 << target\n",
    "        while True:\n",
    "            if cur & left or cur & right:\n",
    "                return res\n",
    "            else:\n",
    "                left <<= 1\n",
    "                right >>= 1\n",
    "                res += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        # 最小的大于等于 target 的和\n",
    "        large = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            next_large = float(\"inf\")\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    if j + x >= target:\n",
    "                        next_large = min(next_large, j + x)\n",
    "                    else:\n",
    "                        g.add(j + x)\n",
    "                next_large = min(next_large, large + x)\n",
    "            f = g\n",
    "            large = next_large\n",
    "        \n",
    "        ans = abs(large - target)\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        dp = [False] * (min(len(mat) * 70, target * 2) + 1)\n",
    "        dp[0] = True\n",
    "        mn = mx = 0\n",
    "        for row in mat:\n",
    "            mn += min(row)\n",
    "            mx = min(target * 2, mx + max(row))\n",
    "            for i in range(mx, -1, -1):\n",
    "                dp[i] = False\n",
    "                for v in row:\n",
    "                    if v <= i and dp[i - v]:\n",
    "                        dp[i] = True\n",
    "                        break\n",
    "        ans = abs(mn - target)\n",
    "        for i, c in enumerate(dp):\n",
    "            if c: ans = min(ans, abs(i - target))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        # 最小的大于等于 target 的和\n",
    "        large = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            next_large = float(\"inf\")\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    if j + x >= target:\n",
    "                        next_large = min(next_large, j + x)\n",
    "                    else:\n",
    "                        g.add(j + x)\n",
    "                next_large = min(next_large, large + x)\n",
    "            f = g\n",
    "            large = next_large\n",
    "        \n",
    "        ans = abs(large - target)\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        # 最小的大于等于 target 的和\n",
    "        large = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            next_large = float(\"inf\")\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    if j + x >= target:\n",
    "                        next_large = min(next_large, j + x)\n",
    "                    else:\n",
    "                        g.add(j + x)\n",
    "                next_large = min(next_large, large + x)\n",
    "            f = g\n",
    "            large = next_large\n",
    "        \n",
    "        ans = abs(large - target)\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "    #     m = len(mat)\n",
    "    #     n = len(mat[0])\n",
    "    #     dp = {0}\n",
    "    #     large = float('inf')\n",
    "    #     for i in range(m):\n",
    "    #         dp1 = set()\n",
    "    #         large1 = float('inf')\n",
    "    #         for s in dp:\n",
    "    #             for num in mat[i]:\n",
    "    #                 if s + num <= target:\n",
    "    #                     dp1.add(s+num)\n",
    "    #                 else:\n",
    "    #                     large = min(large, s+num)\n",
    "    #         dp = dp1\n",
    "    #     ans = abs(large-target)\n",
    "    #     for s in dp:\n",
    "    #         ans = min(ans, abs(s-target))\n",
    "    #     return ans\n",
    "\n",
    "    #DP+bit\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        status = 1\n",
    "        for i in range(m):\n",
    "            cur = 0\n",
    "            for j in range(n):\n",
    "                cur |= status << mat[i][j]\n",
    "            status = cur\n",
    "        i = 0\n",
    "        ans = float('inf')\n",
    "        while status:\n",
    "            if status & 1 == 1:\n",
    "                ans = min(ans, abs(i - target))\n",
    "                if i > target: \n",
    "                    break\n",
    "            status >>= 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        r, c = len(mat), len(mat[0])\n",
    "        n = r * 70 + 1\n",
    "        dp = [0] * (r + 1)\n",
    "        dp[0] = 1\n",
    "        mask = (1 << n) - 1\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(c):\n",
    "                dp[i] |= (dp[i - 1] << mat[i - 1][j])\n",
    "\n",
    "            dp[i] &= mask\n",
    "\n",
    "        ans = float('inf')\n",
    "\n",
    "        for i in range(n):\n",
    "            if dp[-1] & (1 << i):\n",
    "                ans = min(ans, abs(i - target))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        # 最小的大于等于 target 的和\n",
    "        large = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            next_large = float(\"inf\")\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    if j + x >= target:\n",
    "                        next_large = min(next_large, j + x)\n",
    "                    else:\n",
    "                        g.add(j + x)\n",
    "                next_large = min(next_large, large + x)\n",
    "            f = g\n",
    "            large = next_large\n",
    "        \n",
    "        ans = abs(large - target)\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        # 从右到左第i位表示i-1的状态\n",
    "        row, col = len(mat), len(mat[0])\n",
    "        cur = 1\n",
    "        for i in range(row):\n",
    "            temp = 0\n",
    "            for j in range(col):\n",
    "                temp |= cur << mat[i][j] ## 左移n位，代表所有和都加n\n",
    "            cur = temp\n",
    "\n",
    "        res = 0\n",
    "        left = right = 1 << target\n",
    "        while True:\n",
    "            if cur & left or cur & right:\n",
    "                return res\n",
    "            else:\n",
    "                left <<= 1\n",
    "                right >>= 1\n",
    "                res += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        # 1 <= m, n <= 70 ;; 1 <= target <= 800 ；； 1 <= mat[i][j] <= 70\n",
    "        # 和超过某个数就不用考虑了，所以每一行计算的范围是有限的 最多最多1600, \n",
    "        cnt = 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].sort()\n",
    "            cnt += mat[i][0]\n",
    "        \n",
    "        if cnt >= target:\n",
    "            return cnt - target\n",
    "        \n",
    "        up = target + target - cnt  # 和超过这个值就不用计算了\n",
    "        s = set([x for x in mat[0] if x <= up])\n",
    "        for row in mat[1:]:\n",
    "            new_s = set()\n",
    "            for x in s:\n",
    "                for y in row:\n",
    "                    if x + y > up:\n",
    "                        break\n",
    "                    new_s.add(x+y)\n",
    "            s = new_s\n",
    "        \n",
    "        return min(abs(x-target) for x in s)\n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        r, c = len(mat), len(mat[0])\n",
    "\n",
    "        # dp = [[0] * (r * 70 + 1) for _ in range(r + 1)]\n",
    "        dp = [0] * (r + 1)\n",
    "        dp[0] = 1\n",
    "        mask = (1 << (r * 70 + 1)) - 1\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(c):\n",
    "                dp[i] |= (dp[i - 1] << mat[i - 1][j])\n",
    "\n",
    "            dp[i] &= mask\n",
    "\n",
    "        ans = float('inf')\n",
    "\n",
    "        for i in range(r * 70 + 1):\n",
    "            if dp[-1] & (1 << i):\n",
    "                ans = min(ans, abs(i - target))\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        # 最小的大于等于 target 的和\n",
    "        large = float(\"inf\")\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            next_large = float(\"inf\")\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    if j + x >= target:\n",
    "                        next_large = min(next_large, j + x)\n",
    "                    else:\n",
    "                        g.add(j + x)\n",
    "                next_large = min(next_large, large + x)\n",
    "            f = g\n",
    "            large = next_large\n",
    "        \n",
    "        ans = abs(large - target)\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        if n == 1: return abs(sum([row[0] for row in mat]) - target)\n",
    "        s = set([0])\n",
    "        for row in mat:\n",
    "            ns = set()\n",
    "            for num in row:\n",
    "                for nb in s:\n",
    "                    ns.add(nb + num)\n",
    "            s = ns\n",
    "        return min([abs(target - num) for num in s])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        q = set([0])\n",
    "        for x in mat:\n",
    "            tmp = q\n",
    "            q = set()\n",
    "            for y in tmp:\n",
    "                for add in x:\n",
    "                    z = y + add\n",
    "                    if z <= 2 * target:\n",
    "                        q.add(z)\n",
    "        if not q:\n",
    "            return sum(min(x) for x in mat) - target\n",
    "        return min(abs(x - target) for x in q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        s = {0}\n",
    "        for m in mat:\n",
    "            s0 = set()\n",
    "            for x in m:\n",
    "                for k in s:\n",
    "                    s0.add(k + x)\n",
    "            s = s0\n",
    "        \n",
    "        return min(abs(_ - target) for _ in s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m = len(mat)\n",
    "        ans = {0}\n",
    "        now_max_num = inf\n",
    "        for i in range(m):\n",
    "            new_dict = set()\n",
    "            max_num = inf\n",
    "            for num in mat[i]:\n",
    "                for j in ans:\n",
    "                    if j+num<=target:\n",
    "                        new_dict.add(j+num)\n",
    "                    else:\n",
    "                        max_num = min(max_num,j+num)\n",
    "                max_num = min(now_max_num+num,max_num)\n",
    "            now_max_num = max_num\n",
    "            ans = new_dict\n",
    "        if target in ans:\n",
    "            return 0\n",
    "        elif ans:\n",
    "            return min(min([target-i for i in ans]),now_max_num-target)\n",
    "        else:\n",
    "            return now_max_num-target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "\n",
    "        vis = {0}\n",
    "        for g in mat:\n",
    "            c = set()\n",
    "            for num in g:\n",
    "                for p in vis:\n",
    "                    c.add(p + num)\n",
    "            vis = c\n",
    "        ans = inf\n",
    "        for num in vis:\n",
    "            if abs(num - target) < ans:\n",
    "                ans = abs(num - target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cur = 1 ## 初始状态只有一个和：0\n",
    "        for i in range(m):\n",
    "            tmp = 0\n",
    "            for j in range(n):\n",
    "                tmp |= cur << mat[i][j] ## 左移n位，代表所有和都加n\n",
    "            cur = tmp\n",
    "        res = 0\n",
    "        left = right = 1 << target\n",
    "        while True:\n",
    "            if cur & left or cur & right:\n",
    "                return res\n",
    "            else:\n",
    "                left <<= 1\n",
    "                right >>= 1\n",
    "                res += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int: \n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        tsum = set(mat[0])\n",
    "        for i in range(1,m):\n",
    "            tmp = set()\n",
    "            for j in range(n):\n",
    "                for ts in tsum:\n",
    "                    if(ts > target):\n",
    "                        continue\n",
    "                    tmp.add(ts+mat[i][j])\n",
    "\n",
    "            num = min(mat[i])\n",
    "            for ts in tsum:\n",
    "                tmp.add(ts+num)\n",
    "            tsum = tmp\n",
    "        result = float('inf')\n",
    "        for t in tsum:\n",
    "            result = min(result, abs(t-target))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        dp = {0}  # Initialize a set with the base case\n",
    "\n",
    "        for i in range(n):\n",
    "            next_dp = set()  # Use a set for the next DP state\n",
    "            for num in mat[i]:\n",
    "                for val in dp:\n",
    "                    next_dp.add(val + num)\n",
    "            dp = next_dp\n",
    "\n",
    "        ans = float('inf')\n",
    "        for val in dp:\n",
    "            ans = min(ans, abs(val - target))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j+x)\n",
    "            f = g \n",
    "        ans = inf \n",
    "        for x in f:\n",
    "            ans = min(ans,abs(x-target))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        a = {-target}\n",
    "        for ma in mat:\n",
    "            b = set()\n",
    "            for m in ma:\n",
    "                for i in a:\n",
    "                    b.add(m+i)\n",
    "            a = b\n",
    "        return min(abs(x) for x in a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "#         f = set([0])\n",
    "\n",
    "#         r, c = len(mat), len(mat[0])\n",
    "\n",
    "#         for i in range(r):\n",
    "#             g = set()\n",
    "#             for j in range(c):\n",
    "#                 for ele in f:\n",
    "#                     g.add(ele + mat[i][j])\n",
    "\n",
    "#             f = g\n",
    "\n",
    "        \n",
    "#         ans = float('inf')\n",
    "\n",
    "#         for e in f:\n",
    "#             ans = min(ans, abs(e - target))\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        s = {0}\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            s0 = set()\n",
    "            for x in mat[i]:\n",
    "                for k in s:\n",
    "                    s0.add(k + x)\n",
    "            s = s0\n",
    "        \n",
    "        return min(abs(_ - target) for _ in s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "\n",
    "        dp = {0}\n",
    "        for i in range(n):\n",
    "            tmp = set()\n",
    "            for num in mat[i]:\n",
    "                for j in dp:\n",
    "                    tmp.add(j + num)\n",
    "            dp = tmp\n",
    "        ans = 4900\n",
    "        for p in dp:\n",
    "            ans = min(ans, abs(p - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        v = set([0])\n",
    "        for line in mat :\n",
    "            vn = set()\n",
    "            for n in line :\n",
    "                for vt in v :\n",
    "                    vn.add(vt+n)\n",
    "            v = vn\n",
    "        mint = 1e99\n",
    "        for t in v :\n",
    "            mint = min(mint, abs(t-target))\n",
    "        return mint"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j+x)\n",
    "            f = g \n",
    "        ans = inf \n",
    "        for x in f:\n",
    "            ans = min(ans,abs(x-target))\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "    #     m = len(mat)\n",
    "    #     n = len(mat[0])\n",
    "    #     dp = [set() for _ in range(m+1)]\n",
    "    #     dp[0].add(0)\n",
    "    #     for i in range(m):\n",
    "    #         for s in dp[i]:\n",
    "    #             for j in range(n):\n",
    "    #                 dp[i+1].add(s+mat[i][j])\n",
    "    #     ans = float('inf')\n",
    "    #     for s in dp[i+1]:\n",
    "    #         ans = min(ans, abs(s-target))\n",
    "    #     return ans\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m = len(mat)\n",
    "        ans = {0}\n",
    "        for i in range(m):\n",
    "            new_dict = set()\n",
    "            for num in mat[i]:\n",
    "                for j in ans:\n",
    "                    new_dict.add(j+num)\n",
    "            ans = new_dict\n",
    "        return min([abs(i-target) for i in ans])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "\n",
    "        vis = {0}\n",
    "        for g in mat:\n",
    "            c = set()\n",
    "            for num in g:\n",
    "                for p in vis:\n",
    "                    c.add(p + num)\n",
    "            vis = c\n",
    "        ans = inf\n",
    "        for num in vis:\n",
    "            if abs(num - target) < ans:\n",
    "                ans = abs(num - target)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        res = {0}\n",
    "        for row in mat:\n",
    "            res = {x + v for x in res for v in row}\n",
    "        res = sorted(list(res))\n",
    "\n",
    "        if target <= res[0]:\n",
    "            return res[0] - target\n",
    "        elif target >= res[-1]:\n",
    "            return target - res[-1]\n",
    "\n",
    "        idx = bisect.bisect_left(res, target)\n",
    "        return min(res[idx] - target, target - res[idx - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        s = {0}\n",
    "        for m in mat:\n",
    "            s0 = set()\n",
    "            for x in m:\n",
    "                for k in s:\n",
    "                    s0.add(k + x)\n",
    "            s = s0\n",
    "        \n",
    "        return min(abs(_ - target) for _ in s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m = len(mat)\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = inf\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dp = {0}\n",
    "        for i in range(m):\n",
    "            dp1 = set()\n",
    "            for s in dp:\n",
    "                for num in mat[i]:\n",
    "                    dp1.add(s+num)\n",
    "            dp = dp1\n",
    "        ans = float('inf')\n",
    "        for s in dp:\n",
    "            ans = min(ans, abs(s-target))\n",
    "        return ans\n",
    "    # def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "    #     m, n = len(mat), len(mat[0])\n",
    "    #     # 什么都不选时和为 0\n",
    "    #     f = {0}\n",
    "    #     for i in range(m):\n",
    "    #         best = max(mat[i])\n",
    "    #         g = set()\n",
    "    #         for x in mat[i]:\n",
    "    #             for j in f:\n",
    "    #                 g.add(j + x)\n",
    "    #         f = g\n",
    "        \n",
    "    #     ans = float(\"inf\")\n",
    "    #     for x in f:\n",
    "    #         ans = min(ans, abs(x - target))\n",
    "    #     return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        s = {0}\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for m in mat:\n",
    "            s0 = set()\n",
    "            for x in m:\n",
    "                for k in s:\n",
    "                    s0.add(k + x)\n",
    "            s = s0\n",
    "        \n",
    "        return min(abs(_ - target) for _ in s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        # 什么都不选时和为 0\n",
    "        f = {0}\n",
    "        for i in range(m):\n",
    "            best = max(mat[i])\n",
    "            g = set()\n",
    "            for x in mat[i]:\n",
    "                for j in f:\n",
    "                    g.add(j + x)\n",
    "            f = g\n",
    "        \n",
    "        ans = float(\"inf\")\n",
    "        for x in f:\n",
    "            ans = min(ans, abs(x - target))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        dp = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ceil = sum(max(a) for a in mat)\n",
    "        low = sum(min(a) for a in mat)\n",
    "        if ceil > target:\n",
    "            if low > target:\n",
    "                return abs(low-target)\n",
    "            ceil = min(target+target-low, ceil)\n",
    "        \n",
    "        pre = {0}\n",
    "        for ls in mat:\n",
    "            cur = set()\n",
    "            for num in ls:\n",
    "                cur |= {p+num for p in pre}\n",
    "            pre = {num for num in cur if num <= ceil}\n",
    "        return min(abs(x-target) for x in pre)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\r\n",
    "        # 取出的和值范围在 [m, m * 70] \r\n",
    "        # 枚举值 判断是否能取到 \r\n",
    "        n = len(mat) \r\n",
    "        for m in mat:\r\n",
    "            m.sort() \r\n",
    "        mn = sum(x[0] for x in mat)\r\n",
    "        mx = sum(x[-1] for x in mat) \r\n",
    "        if mn >= target:\r\n",
    "            return mn - target\r\n",
    "        if mx <= target:\r\n",
    "            return target - mx  \r\n",
    "        mx = 2 * target + 5 \r\n",
    "        dp = [[False] * (mx + 1) for _ in range(n + 1)] \r\n",
    "        dp[0][0] = True  \r\n",
    "        for i in range(n):\r\n",
    "            for j in range(mx + 1):\r\n",
    "                for x in mat[i]:\r\n",
    "                    if x <= j:\r\n",
    "                        dp[i + 1][j] |= dp[i][j - x]\r\n",
    "                    else:\r\n",
    "                        break \r\n",
    "                    if dp[i + 1][j]:\r\n",
    "                        break\r\n",
    "        res = inf \r\n",
    "        for j in range(mx + 1):\r\n",
    "            if dp[n][j]:\r\n",
    "                res = min(res, abs(target - j))\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\r\n",
    "        # 取出的和值范围在 [m, m * 70] \r\n",
    "        # 枚举值 判断是否能取到 \r\n",
    "        n = len(mat) \r\n",
    "        for m in mat:\r\n",
    "            m.sort() \r\n",
    "        mn = sum(x[0] for x in mat)\r\n",
    "        mx = sum(x[-1] for x in mat) \r\n",
    "        if mn >= target:\r\n",
    "            return mn - target\r\n",
    "        if mx <= target:\r\n",
    "            return target - mx  \r\n",
    "        mx = 2 * target + 5 \r\n",
    "        dp = [[False] * (mx + 1) for _ in range(n + 1)] \r\n",
    "        dp[0][0] = True  \r\n",
    "        for i in range(n):\r\n",
    "            for j in range(mx + 1):\r\n",
    "                for x in mat[i]:\r\n",
    "                    if x <= j:\r\n",
    "                        dp[i + 1][j] |= dp[i][j - x]\r\n",
    "                    else:\r\n",
    "                        break \r\n",
    "                    if dp[i + 1][j]:\r\n",
    "                        break\r\n",
    "        res = inf \r\n",
    "        for j in range(mx + 1):\r\n",
    "            if dp[n][j]:\r\n",
    "                res = min(res, abs(target - j))\r\n",
    "                if j >= target:\r\n",
    "                    break \r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m = len(mat)\n",
    "\n",
    "        f = set()\n",
    "        for num in mat[0]:\n",
    "            f.add(num)\n",
    "\n",
    "        for i in range(1, m):\n",
    "            g = f.copy()\n",
    "            f = set()\n",
    "            for num in mat[i]:\n",
    "                for j in g:\n",
    "                    f.add(j + num)\n",
    "\n",
    "        res = None\n",
    "        for num in f:\n",
    "            if res is None or res > abs(num - target):\n",
    "                res = abs(num - target)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\r\n",
    "        # 取出的和值范围在 [m, m * 70] \r\n",
    "        # 枚举值 判断是否能取到 \r\n",
    "        n = len(mat) \r\n",
    "        for m in mat:\r\n",
    "            m.sort() \r\n",
    "        mn = sum(x[0] for x in mat)\r\n",
    "        mx = sum(x[-1] for x in mat) \r\n",
    "        if mn >= target:\r\n",
    "            return mn - target\r\n",
    "        if mx <= target:\r\n",
    "            return target - mx  \r\n",
    "        mx = 2 * target + 5 \r\n",
    "        dp = [[False] * (mx + 1) for _ in range(n + 1)] \r\n",
    "        dp[0][0] = True  \r\n",
    "        for i in range(n):\r\n",
    "            for j in range(mx + 1):\r\n",
    "                for x in mat[i]:\r\n",
    "                    if x <= j:\r\n",
    "                        dp[i + 1][j] |= dp[i][j - x]\r\n",
    "                    else:\r\n",
    "                        break \r\n",
    "        res = inf \r\n",
    "        for j in range(mx + 1):\r\n",
    "            if dp[n][j]:\r\n",
    "                res = min(res, abs(target - j))\r\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        res = {0}\n",
    "        for row in mat:\n",
    "            # 设置一个res放前面几行之和，然后遍历当前行的元素，分别加上去。由于res是一个set，所以自动去重。\n",
    "            res = {x + v for x in res for v in row}\n",
    "            print(res)\n",
    "        res = sorted(list(res))\n",
    "\n",
    "        if target <= res[0]:\n",
    "            return res[0] - target\n",
    "        elif target >= res[-1]:\n",
    "            return target - res[-1]\n",
    "\n",
    "        idx = bisect.bisect_left(res, target)\n",
    "        \n",
    "\n",
    "        return min(res[idx] - target, target - res[idx - 1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "\n",
    "        minn=sum(min(i) for i in mat)\n",
    "        ans=abs(minn-target)\n",
    "\n",
    "        dp=[[0]*(4902) for i in range(m+1)]\n",
    "        dp[0][0]=1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(len(dp[-1])-1,-1,-1):\n",
    "                if dp[i][j]:\n",
    "                    for y in mat[i]:\n",
    "                        dp[i+1][j+y]=1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        ans=inf\n",
    "        for i in range(len(dp[-1])):\n",
    "            if dp[-1][i]:\n",
    "                ans=min(ans,abs(target-i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        max_sum = sum([max(x) for x in mat])\n",
    "        dp = [[False] * (max_sum + 1) for _ in range(m + 1)]\n",
    "        dp[0][0] = True\n",
    "        for i in range(m):\n",
    "            for j in range(1, min(70 * (i + 1) + 1, max_sum + 1)):\n",
    "                for k in mat[i]:\n",
    "                    if j - k >= 0:\n",
    "                        if dp[i][j - k]:\n",
    "                            dp[i + 1][j] = True\n",
    "                            break\n",
    "        ans = inf\n",
    "        for i in range(1, max_sum + 1):\n",
    "            if dp[m][i]:\n",
    "                res = abs(target - i)\n",
    "                if res < ans:\n",
    "                    ans = res\n",
    "                if ans == 0:\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        minn, maxn = 0, 0\n",
    "        n = len(mat)\n",
    "        for ls in mat:\n",
    "            a, b = max(ls), min(ls)\n",
    "            minn += b\n",
    "            maxn += a\n",
    "        if minn>=target:\n",
    "            return minn-target\n",
    "        if maxn<=target:\n",
    "            return target-maxn\n",
    "        f = [[False]*(maxn+1) for _ in range(n+1)]\n",
    "        f[0][0]=True\n",
    "        for i in range(n):\n",
    "            for j in range(maxn+1):\n",
    "                for x in mat[i]:\n",
    "                    if f[i][j-x]:\n",
    "                        f[i+1][j]=True\n",
    "                        break\n",
    "        ret = inf\n",
    "        for j in range(minn, maxn+1):\n",
    "            if f[-1][j]:\n",
    "                ret = min(ret, abs(j-target))\n",
    "        return ret\n",
    "        @cache\n",
    "        def dfs(i, j): # 前i行中能否选出和恰好是j\n",
    "            if i<0:\n",
    "                return True if j==0 else False\n",
    "            ans = False\n",
    "            for x in mat[i]:\n",
    "                ans |= dfs(i-1, j-x)\n",
    "            return ans\n",
    "        ret = inf\n",
    "        for x in range(minn, maxn+1):\n",
    "            if dfs(n-1, x):\n",
    "                ret = min(ret, abs(x-target))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        r, c = len(mat), len(mat[0])\n",
    "\n",
    "        dp = [[False] * (r * 70 + 1) for _ in range(r + 1)]\n",
    "\n",
    "        dp[0][0] = True\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            flag = False\n",
    "            for j in range(len(dp[0])):\n",
    "\n",
    "                if flag and j > 2 * target:\n",
    "                    break\n",
    "                \n",
    "                dp[i][j] = any(dp[i - 1][j - ele] for ele in mat[i - 1] if j - ele >= 0)\n",
    "                if dp[i][j] and j <= target:\n",
    "                    flag = True\n",
    "                \n",
    "                if dp[i][j] and j >= target:\n",
    "                    break\n",
    "\n",
    "        \n",
    "        ans = float('inf')\n",
    "\n",
    "        for i, flag in enumerate(dp[-1]):\n",
    "            if flag:\n",
    "                ans = min(ans, abs(i - target))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        possibleSums = [set() for _ in range(len(mat))]\n",
    "        possibleSums[0] = set(mat[0])\n",
    "        for i in range(1, len(mat)):\n",
    "            nlarge = 10 ** 10\n",
    "            for j in range(len(mat[i])):\n",
    "                for s in possibleSums[i - 1]:\n",
    "                    if s + mat[i][j] < 800:\n",
    "                        possibleSums[i].add(s + mat[i][j])\n",
    "                    else:\n",
    "                        nlarge = min(nlarge, s + mat[i][j])\n",
    "                if nlarge != 10 ** 10:\n",
    "                    possibleSums[i].add(nlarge)\n",
    "\n",
    "        res = 10 ** 4\n",
    "        print(possibleSums)\n",
    "        for v in possibleSums[-1]:\n",
    "            # print(v, target)\n",
    "            res = min(res, abs(target - v))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        ans = abs(target - sum(mat[i][0] for i in range(m)))\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, cnt):\n",
    "            nonlocal ans\n",
    "            if ans == 0:\n",
    "                return \n",
    "            if cnt - target >= ans:\n",
    "                return\n",
    "            if idx == m:\n",
    "                ans = min(ans, abs(cnt - target))\n",
    "                return \n",
    "\n",
    "            for j in range(n):\n",
    "                dfs(idx + 1, cnt + mat[idx][j])\n",
    "\n",
    "        dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        for i in range(len(mat)):\n",
    "            mat[i].sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, t: int) -> int:\n",
    "            if i < 0:\n",
    "                return abs(t)\n",
    "            res = int(1e8)\n",
    "            for num in mat[i]:\n",
    "                res = min(res, dfs(i-1, t-num))\n",
    "                if t-num <= 0 or res == 0:\n",
    "                    break\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(mat)-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        for i in range(len(mat)):\n",
    "            mat[i].sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, t: int) -> int:\n",
    "            if i < 0:\n",
    "                return abs(t)\n",
    "            res = int(1e8)\n",
    "            for num in mat[i]:\n",
    "                res = min(res, dfs(i-1, t-num))\n",
    "                if t-num <= 0 or res == 0:\n",
    "                    break\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(mat)-1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].sort()\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            if i == m:\n",
    "                return abs(j - target)\n",
    "            if j > target:\n",
    "                return dfs(i + 1, j + mat[i][0])\n",
    "            res = inf\n",
    "            for idx, k in enumerate(mat[i]):\n",
    "                if idx > 0 and j + mat[i][idx-1] >= target:\n",
    "                    break\n",
    "                res = min(res, dfs(i+1, j+k))\n",
    "            return res\n",
    "        return dfs(0, 0)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        n,m = len(mat), len(mat[0])\n",
    "        @cache\n",
    "        def f(indx, tar):\n",
    "            if indx == n:\n",
    "                return abs(tar)\n",
    "            if tar <= 0:\n",
    "                return f(indx+1, tar-min(mat[indx]))\n",
    "            res = inf\n",
    "            for a in mat[indx]:\n",
    "                res = min(res, f(indx+1, tar-a))\n",
    "            return res\n",
    "        return f(0,target)                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimizeTheDifference(self, mat: List[List[int]], target: int) -> int:\n",
    "        for i in range(len(mat)):\n",
    "            mat[i].sort()\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, t: int) -> int:\n",
    "            if i < 0:\n",
    "                return abs(t)\n",
    "            res = int(1e8)\n",
    "            for num in mat[i]:\n",
    "                res = min(res, dfs(i-1, t-num))\n",
    "                if t-num <= 0:\n",
    "                    break\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(mat)-1, target)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
